#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

def max_array_sum(array):
    if not array:
        return None, None, None

    l = len(array)
    # end_with_sum = [0] * l
    max_value_global = array[0]
    max_value_till_i = max_value_global
    max_begin, max_end = 0, 0
    left = right = 0

    for idx in range(1, l):
        # max_value_till_i : 结尾为idx 的数组最大值.
        v1 = max_value_till_i + array[idx]
        v2 = array[idx]
        right = idx
        if v1 >= v2:
            # 如果想要array尽量长, 就在这里使用">=", 否则使用">"
            max_value_till_i = v1
        else:
            max_value_till_i = v2
            left = idx

        if max_value_global < max_value_till_i:
            # print('mat %s %s', left, right)
            max_value_global = max_value_till_i
            max_begin, max_end = left, right


    return max_begin, max_end, max_value_global


def test():
    max_begin, max_end, sum = array = max_array_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4])
    print(max_begin, max_end, sum)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
